BackTracking(回溯法) 是窮舉法的一種。
其概念是先逐步列舉出所有可能,然後逐步排查不可能的部份。
當遇到不可能的部份,則退回上一個分支源頭,從該點往下繼續探查。
具體的作法是,可以透過決策樹把可能的路徑描繪出來,透過問題限制來排查問題。
特別適合用於約束滿足問題,這類問題的解答俱備一定的約束性,所以適合用BackTracking(回溯法)。
經典的問題如八皇后問題,就適合用 Backtracking。
8 by 8 的棋盤要擺放八個西洋棋的皇后,要求找出所有可以不讓皇后相互攻擊的放法。
下圖是 4 皇后的圖解
中華武士會會長宮羽田曾對徒弟馬三說:
老猿掛印回首望,關隘不在掛印,而是回頭
https://zh.wikipedia.org/zh-tw/%E5%9B%9E%E6%BA%AF%E6%B3%95
https://zh.wikipedia.org/zh-tw/%E5%85%AB%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98
https://zh.wikipedia.org/zh-tw/%E7%B4%84%E6%9D%9F%E6%BB%BF%E8%B6%B3%E5%95%8F%E9%A1%8C